The invention relates to allocating resource requests to the available resources. More specifically, the invention relates to distributing information requests to servers capable of storing and providing the requested information.
In large distributed information systems there are servers that store information and there are clients that request information. The World Wide Web (xe2x80x9cWebxe2x80x9d) is an example of a distributed information system. There are web sites, which act as servers, and there are clients, which are computers used by people to obtain information from the servers. The users request information from the web sites and the web sites respond to the requests by providing the requested information in the form of data, documents, files, or web pages.
Immense growth of the Web places great demands on the infrastructure of the Internet that provides the physical connections for the Web. Service providers invest vast sums of money in Internet infrastructure in an attempt to provide acceptable performance despite increasing data demand. Acceptable performance generally implies little or no delay in accessing information. Two causes of delay are heavy communication loading a part of a network and a large number of requests loading a particular server. When part of the network becomes congested with too much traffic, communication over that part of the network becomes unreliable and slow. Similarly, when too many requests are directed at a single server, the server becomes overloaded, or xe2x80x9cswamped.xe2x80x9d
One of these problems can cause the other, in part because network software is typically designed to repeat requests that are not responded to promptly. For example, if a server is overloaded, it will not respond to requests quickly, and requests may be resent, thereby increasing network traffic. If a network is overloaded, a request may not reach a server quickly, and a duplicate request may be sent to the server before the server had a chance to respond to the first request, thereby increasing the load on the server. Both network overload and server overload lead to delays in retrieving information.
A server can become overloaded for various reasons. A server storing a few documents that have very high access rates can become overloaded. An example of this kind of server is a web site that becomes very popular such as a site reporting results of a popular sports event. A server responsible for such a site can become overloaded with a large volume of requests for a one or a small number of documents containing the latest information on the event. Another type of server that can become overloaded is a server storing a large number of documents each of which is accessed at normal or even relatively low access rates. The server becomes overloaded as it attempts to serve a large number of requests for many different documents. An example of this kind of server is a server for a large organization, such as a library, that serves a vast number of documents that are accessed on a regular basis.
A general strategy employed to reduce both network traffic and overloaded servers is replication accomplished by caching. Copies of frequently requested documents can be stored throughout the network, thereby spreading the work of serving the documents across several servers. In one approach, several clients share a cache server in a manner that is transparent to the people using it. Client requests are forwarded through the cache server, which keeps copies of frequently requested documents and attempts to satisfy requests with a cached copy. If the cache server has a copy of the document, then the request can be answered immediately with the requested document. If the cache server does not have a copy, then the cache server can request a copy of the document from the original site. When the cache server receives a copy of the document from another cache server or from the original site for the document, it can then answer the client""s request. Subsequent requests for that document can be serviced by the cache because it has a copy of the document. Thus, the load on the original site for the document is reduced because the original site does not need to be involved in every request.
Referring to FIG. 1A, three clients, Client One 110, Client Two 111, and Client Three 112, each request documents Doc1, Doc2, and Doc3 respectively via Cache Server A 100. The cache server answers all three of these requests in a manner that is transparent to the users. If Server A 100 does not have the documents requested by Client One 110, Client Two 111, and Client Three 112, it requests the documents from the Original Sites 102, 104 for the documents. Once it receives the documents it sends the documents to the Clients 110-112.
Caching can reduce network traffic if the cached copy is close, in the network topology sense, to the requester because fewer network links and resources are used to retrieve the information. Caching can also relieve an overloaded server because some of the requests that would normally be routed to the original site can be served by a cache server, and so the number of requests made of the original site is reduced. There is a tradeoff of a greater performance benefit if more clients share the same cache server that is balanced against an increased likelihood that the cache server itself will become overloaded.
One approach to solving this dilemma is to use a group of servers that function together as a cache. Responsibility for answering requests is divided among the group. There are many ways to divide responsibility among the group of servers. One way is to have a client""s request for a document be directed to an arbitrary one of the servers of the group of cache servers. If a copy of the document is stored in that server, it is transmitted to the client. If a copy is not stored in that server, the request is forwarded to the original site of the document. This approach divides the load among the servers, thereby preventing overload of any particular server. A client needs to know which servers are available, but the client does not need information about the servers to choose one. One disadvantage of this approach is that each of the servers will request each document from the original site for that document. This could load the original site as the number of cache servers increases.
Alternatively, the server could, if it does not have a copy of the document, first forward the request to the other cache servers. One disadvantage of this technique is that as the number of participating servers grows, the number of messages between the cache servers can become problematic.
Another approach also uses a group of servers but allocates responsibility for documents to particular servers. As part of this approach, the client is informed about the allocation of documents to servers so it can address a request to the server with responsibility for that document. Instead of arbitrarily choosing a cache, a client chooses the cache server allocated to the document requested. For this approach to be successful, it cannot be unduly burdensome on the client to determine which cache server to direct a document request. It is also necessary to balance the load appropriately among the caches. For example, even if all documents are accessed by clients at the same rate, if some caches contain more documents than others, those caches will have more requests to service, and may become overloaded.
In the context of caching, it would be unduly burdensome to maintain a list of all the documents available in the cache servers. Such a list would have to be maintained as documents were added and deleted from the original site. An alternative approach is for clients to use a standard hash function to determine from which server to request a document. In FIG. 1B, a standard hash function (h) is used by the clients to choose among three cache servers. Client One 110 requests Doc1 from Server A 100 since h(Doc1)=Server A. Client Two 111 requests Doc2 from Server B 121 since h(Doc2)=Server B. In this example, Server B 121 does not have the requested document, so it requests the document from the original site for Doc2104. Client Three 112 requests Doc3 from Server C 122 since h(Doc3)=Server C. Server C 122 does not have Doc3, so Server C 122 requests the document from Doc3""s Original Site 104. In this example, after obtaining a copy of the requested document, Server C 122 stores the document. When Client Four 140 requests Doc3, it also requests it from Server C 122, since h(Doc3)=Server C. Server C 122 already has Doc3 since it previously obtained a copy to service the request from Client Three 112. Server C 122 is able to respond to the request without placing any additional load on the network between Server A 100 and Server C 122 and without requiring Server A 100 to take on the load of the request from Client Four 140. The hash function serves as a method for users to agree on which server is responsible for a document.
Hashing with a standard hash function has the same effect as distributing the items randomly, because a standard hash function will tend to distribute items approximately evenly throughout its output range. This is very desirable because a random assignment of documents to servers will spread the load of serving the active set of documents among the servers. An example of a standard hash function that can be used to distribute documents to servers is f(d)=((ad+b) mod n), where document names (d) are integers, there are (n) servers {0, 1, 2, . . . , nxe2x88x921}, and (a) and (b) are some fixed choice of integers. For most choices of (a) and (b) the function distributes documents roughly evenly over the servers.
Referring to FIG. 2A, an original distribution of one hundred thirty-four documents to servers is shown. Here, the document names are integers, and there are 13 servers {1, 2, . . . , 13}. Some servers store many more documents than others, and thus in the model of equal access frequency these servers are more heavily loaded. FIG. 2B shows the distribution of documents to servers using a standard hash function such as f(d)=((ad+b) mod 13). In the distribution of FIG. 2B, no server is responsible for a disproportionately large share of documents.
One disadvantage of using a standard hash function to allocate documents, and, therefore, documents requests, to servers is that a change in the number of servers can be disruptive to the caching scheme. In networks such as the Internet, servers frequently may be added to, or removed from, the network, and these changes need to be incorporated into a caching scheme. With the hash function just discussed, adding a server to the scheme requires changing the range of the hash function to include the new server. Changing the range of the hash function may result in many documents changing location. For example, if there are (n) servers and the hash function mapping documents to servers is f(d)=((ad+b) mod n), then when a server is added, the hash function is changed to fxe2x80x2(d)=((ad+b) mod (n+1)).
An example of the change of mapping of documents to servers caused by a change in the number of servers is shown in FIG. 3A and FIG. 3B. FIG. 3A illustrates the assignment of 10 documents to 4 servers using the hash function f(d)=(d+1) mod 4. FIG. 3B illustrates the assignment after one additional server is added and the hash function is changed to f(d)=(d+1) mod 5. In FIG. 3B, circles show the mapping with 4 servers and squares show the mapping with 5 servers. Almost every document is mapped to a different server as a result of the addition of the new server.
A characteristic of this hash function and many other standard hash functions is that when the range of the function is modified, the mapping is completely reshuffled. That is, most documents are mapped to different servers than they were mapped to before the change. A complete reshuffling of the distribution of documents to servers is quite disruptive to a caching scheme. After each server is added, every server will need to request copies of the documents for which it is now responsible from the original document sites. Adding or removing a server, therefore, places a load on the cache servers and the original sites.
In addition to the problem of reshuffling data upon a change in the number of servers there is another complication. When a change in the number of servers occurs, users have to be notified of the change so that they can start to use a new hash function that includes the new number of cache servers. If users can be notified of the change simultaneously this does not present a problem, but in a network such as the Internet, such global synchronous notification is very difficult to achieve. It is feasible, however, to assume that notification about server changes can be done by slowly propagating the information from system to system, for example in a manner similar to the way that network news is distributed. As a consequence, the set of cache servers recognized by each user may differ widely. A user""s xe2x80x9cviewxe2x80x9d is a term for the set of servers that the user knows exist. Because synchronous notification is impossible, different users are very likely to have different views.
The example of FIG. 3A and FIG. 3B can also be used to illustrate the effects of multiple views of the servers on the caching scheme. If some users a re aware of the addition of server 4 and some of the users are not aware of the addition of server 4, then there are two views of the system held by users. One view (the xe2x80x9coldxe2x80x9d view) is {0,1,2,3} and the other view (the xe2x80x9cnewxe2x80x9d view) is {0,1,2,3,4}. Users not aware of the addition of server 4 use the old mapping of documents to servers represented by the circles. Users aware of the new server 4 use the new mapping represented by the squares, which is almost a complete reshuffling of the old mappings. To work in a scheme where users have different views, cache servers must serve requests for the documents allocated in all users"" views. As a result, the number of documents that a server is responsible for, in this example in which one server was added, is almost doubled. For example, users with the old view use server 2 for the documents 5 and 29, while users with the new view use server 2 for documents 11 and 36. Server 2 will receive requests for all of these documents, thus effectively doubling the requirements on the server. The total number of documents that a server is responsible for is called its load. Referring to FIG. 3B, the load of server 2 is 4 since there are two documents from each view. Using a standard hash function, each view increases the load.
A further complication results from having a single document assigned to different cache servers in different views. If there are many clients with many different views, then a large number of cache servers can be responsible for a document. This in turn implies that the original site is more likely to become overloaded with requests for copies from multiple cache servers. For example, referring to FIG. 3A and FIG. 3B, document 7 is assigned to server 0 in the view {0,1,2,3} and to server 3 in the view {0,1,2,3,4}. The original site for document 7 has to supply a copy to both server 0 and server 3. The total number of servers to which a document is assigned is called the spread of the document. For example, the spread of document 5 in the example of FIG. 3A and FIG. 3B is 2. Using a standard hash function, the spread of a document increases with the number of views.
In summary, the use of standard hash functions to identify a resource (for example, a cache server) for a particular request (for example, a document) results in a greatly increased load and spread when the number of resources (cache servers) changes, and there are, accordingly, multiple views. This drawback can have a great impact on performance when the number of documents and servers is large.
It should be noted that the approach of allocating responsibility for each document to different servers is less effective when the cache is experiencing a large number of requests for the same small number of documents. The large number of requests will all go to the small number of servers responsible for the small number of documents The small number of servers are likely to be overloaded by the large number of requests.
One approach for preventing one server from being overloaded by a large number of requests for the same document is to use a group of caches in series between the user and the original site of the document, each of which can service the request for the document. In one embodiment of this approach, if a first cache server does not have a document, it requests the document from another (second) cache and not the original site. The second cache services a defined group of first-level caches. If the second cache does not have the document, the second cache requests the document from yet another (third) cache. The third cache services a defined group of second-level caches. This continues until the last cache in the series does not have the document, at which point the last cache requests the document from the original site. This approach provides cache layers between the first cache and the original site and it spreads the load among the caches at each layer. Different users can use different lists of caches for the same document, thereby spreading the load. The list of servers to request the document from can be derived in various ways.
One approach is to use a tree of caches. In this approach, a user requests a document by requesting the document from a server representing a first node on a tree of caches. If this cache does not have the document, the request is forwarded to the next cache in the tree. If the next cache does not have the document, the request is forwarded from that cache to the next cache and so on. If a document is not stored by any intermediate cache in the tree, the request eventually reaches the root of the tree and is forwarded to the original site of the document. In this approach, a cache retains a copy of any document it obtains for a period of time. An advantage of a cache tree is that a cache receives document requests only from the caches that come before it, and this limits the number of requests that arrive simultaneously. Thus, many requests for a document in a short period of time will only cause one request to the original server of the document, and will not result in cache server overload.
One theoretical disadvantage of this system is that the root receives at least one request for every distinct document requested of the entire cache tree. This can overload the root with requests if the number of distinct document requests grows too large, meaning that this approach suffers from potential scaling problems.
One aspect of the invention is a caching system that prevents server and network overloading and scales gracefully even when clients have multiple views. Resources can be added and removed from a pool of available resources without a reallocation of all or even most of the requests. Only the requests associated with the server added or removed have to be reallocated. This is referred to as xe2x80x9cconsistent hashingxe2x80x9d because for most of the set of requests, the allocation is consistent even as resources are added and removed. Only a subset of all the requests are allocated to different resources. With regard to caching data, consistent hashing avoids increasing load and spread when the number of servers changes.
In another aspect, a series of servers is used that are chosen in a manner that spreads the load associated with a small number of frequently requested documents, and thereby prevents overloading. This is referred to as xe2x80x9cvirtual networks.xe2x80x9d When used together, consistent hashing and virtual networks improve the ability of document servers generally and caching servers in particular to respond to large numbers of requests.
In one aspect, the invention relates to a method and apparatus for distributing a request to one of a plurality of resources that includes mapping the request to a request location in mathematical mapping space, mapping each of the resources to a respective at least one resource location in mathematical mapping space, and allocating the request to one of the resources based on a mathematical relationship between the request and resource locations. An apparatus for distributing a request to one of a plurality of resources includes the plurality of resources and an input receiving a resource request. A mapper in communication with the input maps the request to a request location in a mathematical mapping space and maps each of the plurality of resources to at least one resource locations in the mathematical mapping space. A distributor distributes the request to one of the plurality of resources in response to a mathematical relationship between the locations of the request and resources in the mathematical mapping space.
In one embodiment, the mathematical mapping space is a circle. In one embodiment the request is a data request and the resource is a server. In one embodiment the step of mapping each of the resources to a respective at least one resource location comprises hashing each of the resources to a respective resource location in the mathematical mapping space.
The invention also relates to a computer-readable medium whose contents cause a computer system to distribute a request to one of a plurality of resources. The computer system executes the contents of the computer-readable medium by performing a computer program. The computer program maps the request to a request location in a mathematical mapping space and maps each of the resources to a respective at least one location in the mathematical mapping space. The computer program allocates the request to one of the resources based on a relationship between the request location and the resource locations in the mathematical mapping space.
Another aspect of the invention relates to a method for requesting data from one of a plurality of servers. The method includes generating an virtual network of nodes in response to a data request and randomly choosing a first node on the virtual network of nodes. The method also includes generating a path from the first node to the root node on the virtual network of nodes and mapping at least one node on the path to a respective one of the plurality of servers. The method also includes requesting data from the one of the plurality of servers.
In one embodiment, the step of requesting data from one of the plurality of servers is accomplished with a data request comprising identification of the desired data and a sequence of nodes through which the request should be directed. In one embodiment, the data request also comprises a sequence of servers that should act as the nodes. In one embodiment requesting the data from the server mapped to the chosen node includes transmitting a request from a client to the server. In one embodiment mapping at least one node on the path to a respective one of the plurality of servers comprises calculating a hash function. In one embodiment mapping a node on the path to a respective one of the servers includes mapping the node to a node location and each of the servers to at least one server location in a mathematical mapping space and allocating the node to one of the servers based on a mathematical relationship between the node location and the server locations in the mathematical mapping space.
The invention also relates to an apparatus for requesting data from one of a plurality of servers. The apparatus includes an input receiving a data request and a path generator in communication with the input that randomly chooses a node on an virtual network and generates at least one path of nodes in response to the data request. The apparatus also includes a mapper in communication with the path generator mapping nodes on the at least one path of nodes to one of the plurality of servers. The apparatus also includes an output in communication with the mapper and requesting data from the one of the plurality of servers mapped to the nodes on the at least one path of nodes.
In another aspect, the invention relates to a method for responding to data requests made by a client. The method includes receiving a first data request that includes a sequence of nodes corresponding to a sequence of servers. The method also includes determining whether the data specified in the data request is not available on a selected server. If the data is not available, the method also includes determining a next node from the sequence of nodes, mapping a server to the next node, and requesting the data by transmitting a second data request to the server mapped to the next node.
In one embodiment the step of mapping a server to the next node comprises calculating a hash function. In one embodiment the first data request is substantially similar to the second data request. In one embodiment the second data request includes a sequence of nodes. In one embodiment the method further includes receiving the data from the server mapped to the next node in response to the second data request, determining the total number of times the data in the first data request has been requested, and caching the data requested by the first data request if the count of the number of times the data in the first data request was requested exceeds a threshold. In one embodiment the method includes the step of responding to the first request by transmitting the data.
The invention also relates to an apparatus for responding to data requests made by a client. The apparatus includes an input receiving a first data request that includes a sequence of nodes corresponding to a sequence of servers. The apparatus also includes decision logic determining whether the data specified in the data request is available on a selected server, and if the data is not available determining a next node from the sequence of nodes. The apparatus also includes a mapper mapping a server to the next node. The apparatus also includes an output requesting the data by transmitting a second data request to the server mapped to the next node.